/*
 * @lc app=leetcode.cn id=140 lang=cpp
 *
 * [140] 单词拆分 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<bool>> dp;
    size_t min_len, max_len;
    set<string> dict;
    vector<string> ans;
    string question_s;

    bool findPath(int start_pos, const int length, string &s)
    {
        if (start_pos < length && !dp[start_pos][0])
            return false;
        if (start_pos == length)
        {
            ans.push_back(s);
            return true;
        }

        string src_s = s;
        if(src_s.length() > 0) src_s += ' ';
        for (int i = min_len; i <= max_len && i <= length - start_pos; i++)
        {
            if (dp[start_pos][i])
            {
                s = src_s + question_s.substr(start_pos, i);
                findPath(start_pos + i, length, s);
            }
        }
        s = src_s;
        if(s.length() > 1)
        {
            s.erase(s.end() - 1);
        }
        return false;
    }

    vector<string> wordBreak(string s, vector<string> &wordDict)
    {
        if(s.length() == 0) return {};
        question_s = s;
        min_len = wordDict[0].length();
        max_len = min_len;
        for (auto &it : wordDict)
        {
            dict.insert(it);
            min_len = min(it.length(), min_len);
            max_len = max(it.length(), max_len);
        }

        dp = vector<vector<bool>>(s.length() + 1, vector<bool>(max_len + 1, 0));
        dp[0][0] = true;

        for (int i = 0; i <= s.length() - min_len; i++)
        {
            for (int j = min(max_len, s.length() - i); j >= min_len; j--)
            {
                dp[i][j] = dict.find(s.substr(i, j)) != dict.end();
                if (dp[i][j])
                {
                    dp[i][0] = true;
                }
            }
        }

        string ss;
        findPath(0, s.length(), ss);

        return ans;
    }
};

// int main()
// {
//     string s = "catsanddog";
//     vector<string> v = {"cat", "cats", "and", "sand", "dog"};
//     Solution().wordBreak(s, v);
//     return 0;
// }
// @lc code=end
